/**
 * 给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
 *  3
   / \
  9  20
    /  \
   15   7


 * [
    [15,7],
    [9,20],
    [3]
   ]
 */


// bfs
var levelOrderBottom = function (root) {
    if (root === null) return []
    const queue = [root]
    const outQueue = []
    while (queue.length !== 0) {
        const size = queue.length
        const tempQueue = []
        for (let i = 0; i <= size - 1; i++) { 
            const cur = queue.shift()
            tempQueue.push(cur.val)
            if(cur.left) {queue.push(cur.left)}
            if(cur.right) {queue.push(cur.right)}
        }
        outQueue.unshift(tempQueue)
    }
    return outQueue
};

//递归
var levelOrderBottom = function(root) {
    let result = [];
    if(!root) return result;

    (function run(root, level) {
        if(!result[level]) result[level] = [];
        result[level].push(root.val);

        if(root.left) {
            root.left && run(root.left, level + 1);
        }

        if(root.right) {
            root.right && run(root.right, level + 1);
        }

    })(root, 0)

    return result.reverse();
};